
public class Buvos {
	private int n,a,b,c,d,osszeg;
	private int nNegyzet;
	private int[][] matrix;
	public int sol;
  
	Buvos(int n) {
		sol = 0;
		int val=0;
		this.n = n;
		this.nNegyzet=n*n;
		matrix = new int[n][n];
		osszeg = n*(nNegyzet+1)/2;
	}
	public boolean good(){
		return false;
	}
	
	public boolean solve (int i, int j) {
			if (i==n) {
				i = 0;
				if (++j == n) {    
					sol++;
					System.out.println(sol);
					kiir();
					return true;    
				}
			}
		
		for (int k=1; k<=nNegyzet; k++)
		{
			int val = k;
			if (legal(i,j,val)) {
				matrix[i][j] = val;
				solve(i+1,j);
			}
		}
		matrix[i][j] = 0; 
	    return true;
	}
	
	public boolean legal(int i, int j, int val ) {
		a=0; b=0; c=0; d=0;
		
		for (int k=0; k<n; k++) 
		{
			a+=matrix[i][k];
			b+=matrix[k][j];
			c+=matrix[k][k];
			d+=matrix[k][n-k-1];
		}
		
		for (int m = 0; m<n; m++)
			for (int l=0; l<n; l++)
				if (val == matrix[m][l]) {
					return false;
		}
		if ((i==n-1) && ((b+val)!=osszeg)) {
			return false;
		}
		if ((j==n-1) && ((a+val)!=osszeg)) {
			return false;
		}
		if ((j==n-1) && (i==0) && (d+val!=osszeg))
			return false;
		
		if ((i==n-1) && (j==n-1) && ((a+val != osszeg) || (b+val != osszeg) ||(c+val != osszeg) || (d != osszeg)))
		{
			return false;
		}

		if ((i==n-1) && (j==n-1) && (c+val!=osszeg) ) {
		   return false;
		}	
		
		return true;
	}
	
	public void kiir() {
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++)
				System.out.print(matrix[i][j]+" ");
			System.out.println();
		}
		System.out.println();
		
	}
	
	public static void main(String args[]) {
		Buvos b = new Buvos(3); 
 		b.solve(0,0);
		System.out.println("s=" + b.sol);
	}
	
}
